Leetcode 188. Best Time to Buy and Sell Stock IV 题解

题目链接

Leetcode 188. Best Time to Buy and Sell Stock IV

题目内容

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example1:

Input: [2,4,1], k = 2

Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example2:

Input: [3,2,6,5,0,3], k = 2

Output: 7

Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

解题思路

本题是之前做过的题目中后续系列的题目，也是用的dp的思想进行解题，这题与之前不同的是，可以指定交易的最大次数，所以，当k >= prices.size() / 2时，其每次都可以交易，我们只需看每一次交易会不会赚钱，会赚钱，加到收益中，就可获取最大收益。 那么正常情况的dp状态转移方程呢，我们通过计算k次交易购买最少损耗的钱buys以及k次交易出售能获取的最多的钱sells来获取我们的答案，转态转移方程如下: buys[j] default = INT_MIN, sells[j] default = 0 for each p buys[j] = max(buys[j], sells[j-1] - p) (1<=j<=k) sells[j] = max(sells[j], buys[j] + prices[i]);

最终结果即为我们的sells[k]。

提交detail为

题目代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (k >= prices.size() / 2) {
            int res = 0;
            for (int i = 1; i < prices.size(); ++i)
                res += max(0, prices[i] - prices[i - 1]);
            return res;
        }

        vector<int> buys(k + 1, INT_MIN), sells(k + 1, 0);
        for (int i = 0; i < prices.size(); i++) {
            for (int j = 1; i <= k; ++i) {
                buys[j] = max(buys[j], sells[j - 1] - prices[i]);
                sells[j] = max(sells[j], buys[j] + prices[i]);
            }
        }
        return sells[k];
    }
};